Language/OS - Multiplatform Resource Library/LANGUAGE OS.iso/cpp_libs/intrvews/xgrab.lha/xgrab/ui/OGC/README

Text File | 1990-03-06 | 7.2 KB | 142 lines

Copyright 1988 Hans-J. Boehm, Alan J. Demers
This material may be freely distributed, provided this notice is retained.
This material is provided as is, with no warranty expressed or implied.
Use at your own risk.

GRAB Graph Layout and Browser System
Copyright (c) 1989, Tera Computer Company

  This collector was developed as a part of research projects supported in
part by the National Science Foundation and the Defense Advance Research
Projects Agency.  The SPARC specific code was contributed by Mark Weiser
at Xerox PARC.  Some of the improvements incorporated in this version were
suggested by David Chase at Olivetti Research.

  This is intended to be a general purpose, garbage collecting storage
allocator.  The algorithms used are described in:

Boehm, H., and M. Weiser, "Garbage Collection in an Uncooperative Environment",
Software Practice & Experience, September 1988, pp. 807-820.

  Many of the ideas underlying the collector have previously been explored
by others.  (We discovered recently that Doug McIlroy wrote a more or less
similar collector that is part of version 8 UNIX (tm).)  However none of this
work appears to have been widely disseminated.

  The tools for detecting storage leaks described in the above paper
are not included here.  There is some hope that they might be released
by Xerox in the future.

  Since the collector does not require pointers to be tagged, it does not
attempt to insure that all inaccessible storage is reclaimed.  However,
in our experience, it is more successful at reclaiming unused memory than most
C programs using explicit deallocation.

  In the following, an "object" is defined to be a region of memory allocated
by the routines described below.

  Any objects not intended to be collected must be pointed to either
from other such accessible objects, or from the registers,
stack, data, or statically allocated bss segments.  It is assumed
that all such pointers point to the beginning of the object.  (This does
not disallow interior pointers; it simply requires that there must be a
pointer to the beginning of every accessible object, in addition to any
interior pointers.)
  Note that pointers inside memory allocated by the standard "malloc" are not
seen by the garbage collector.  Thus objects pointed to only from such a
region may be prematurely deallocated.  It is thus suggested that the
standard "malloc" be used only for memory regions, such as I/O buffers, that
are guaranteed not to contain pointers.  Pointers in C language automatic,
static, or register variables, are correctly recognized.
  The collector is designed to minimize stack growth if link fields inside
structures are allocated first.  (Normally only linked lists of lengths
exceeding about 100000 will cause this to be noticable.)
  Signal processing for most signals is deferred during collection.
  As distributed, the collector produces garbage collection statistics
during every collection.  Once the collector is known to operate properly,
these can be suppressed by undefining the appropriate macros at the top
of "runtime.h".  (The given statistics exhibit a few peculiarities.
Things don't appear to add up for a variety of reasons, most notably
fragmentation losses.  These are probably much more significant for the
contrived program "test.c" than for your application.)
  The collector is preconfigured to run on a Sun 3 workstation.  It will
run on Sun 2s if the definition of STACKTOP in runtime.h is changed.
It can also be reconfigured to run on a Vax under Berkeley UNIX, on a Sun 4
under 4.0, or on a Sequent Symmetry. This requires changing a definition at
the beginning of runtime.h.  (On a Sun 4, Makefile needs to be changed as
indicated.  The collector is known not to run on a Sun 4 under at least
some versions of 3.2.  The cause for this is not yet known.)  In all cases
we assume that pointer alignment is consistent with that enforced by the
standard C compilers.
  For other machines, the following are likely to require change:

1.  The parameters at the top of runtime.h
2.  allocobj.c
3.  The top level routine gcollect in alloc.c.  It contains assembly code
    to mark registers.
4.  In-line assembly code in alloc.c.  (The mark algorithm is not recursive,
    but may use the process stack as a marking stack.  This requires direct
    access to the stack pointer.  Changes should be trivial on most
    architectures.)

  For a different UN*X version or different machine using the Motorola 68000,
Vax, SPARC, or 80386 architecture, it should frequently suffice to change
definitions in runtime.h.

  The following routines are intended to be directly called by the user.
Note that only gc_malloc and gc_init are necessary.  The remaining routines
are used solely to enhance performance.  It is suggested that they be used
only after initial debugging.

1)  gc_init()
    - called once before allocation to initialize the collector.

2)  gc_malloc(nbytes)
    - allocate an object of size nbytes.  Unlike malloc, the object is
      cleared before being returned to the user.  (For even better performance,
      it may help to expand the relevant part of gc_malloc in line.
      This is done by the Russell compiler, for example.)  Gc_malloc will
      invoke the garbage collector when it determines this to be appropriate.

3)  gc_malloc_atomic(nbytes)
    - allocate an object of size nbytes that is guaranteed not to contain any
      pointers.  The returned object is not guaranteed to be cleeared.
      (Can always be replaced by gc_malloc, but results in faster collection
      times.  The collector will probably run faster if large character
      arrays, etc. are allocated with gc_malloc_atomic than if they are
      statically allocated.)

4)  gc_free(object)
    - explicitly deallocate an object returned by gc_malloc or
      gc_malloc_atomic.  Not necessary, but can be used to minimize
      collections if performance is critical.

5)  expand_hp(number_of_4K_blocks)
    - Explicitly increase the heap size.  (This is normally done automatically
      if a garbage collection failed to reclaim enough memory.  Explicit
      calls to expand_hp may prevent unnecessarily frequent collections at
      program startup.)

  The global variable dont_gc can be set to a non-zero value to inhibit
collections, e.g. during a time-critical section of code.  (This may cause
otherwise unnecessary exansion of the process' memory.)
  The variable non_gc_bytes, which is normally 0, may be changed to reflect
the amount of memory allocated by the above routines that should not be
considered as a candidate for collection.  Collections are inhibited
if this exceeds a given fraction (currently 3/4) of the total heap size.
The heap is simply expanded instead.  Careless use may, of course, result
in excessive memory consumption.

  The two gc_malloc routines may be declared to return a suitable pointer
type.  It is not intended that runtime.h be included by the user program.
If only gc_malloc is intended to be used, it might be appropriate to define:

#define malloc(n) gc_malloc(n)
#define calloc(m,n) gc_malloc((m)*(n))

  No attempt is made to use obscure names for garbage collector routines
and data structures.  Name conflicts are possible.  (Running "nm gc.o"
should identify names to be avoided.)

  Please address bug reports to [e-mail].